import java.util.*;

/**
 * 没有重复项数字的全排列
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        fun(num, ans, list);
        return ans;
    }

    private void fun(int[] num, ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> list) {
        if(list.size() == num.length) {
            // 注意这里必须new一个新的顺序表进行保存
            ArrayList<Integer> newList = new ArrayList<>(list);
            ans.add(newList);
            return;
        }
        for(int i = 0; i < num.length; i++) {
            if(list.contains(num[i])) {
                continue;
            }
            list.add(num[i]);
            fun(num, ans, list);
            list.remove(list.size() - 1);
        }
    }
}